public class Solution97 {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }
        boolean[] dp = new boolean[s2.length() + 1];
        dp[0] = true;
        for (int i = 0; i <= s1.length(); i++) {
            char a = 0;
            if (i > 0) {
                a = s1.charAt(i - 1);
            }
            for (int j = 0; j <= s2.length(); j++) {
                char c = 0;
                if (i + j > 0) {
                    c = s3.charAt(i + j - 1);
                }
                if (i > 0) {
                    dp[j] = dp[j] && a == c;
                }
                if (j > 0) {
                    dp[j] = dp[j] || (dp[j - 1] && s2.charAt(j - 1) == c);
                }
            }
        }
        return dp[s2.length()];
    }

}
